package com.linyaonan.leetcode.medium._560;

import java.util.HashMap;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 *
 * 子数组是数组中元素的连续非空序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 10^4
 * -1000 <= nums[i] <= 1000
 * -10^7 <= k <= 10^7
 *
 * @author: Lin
 * @date: 2024/9/20
 */
public class SubarraySumEqualsK {


    /**
     * 子序列的要求为连续，并且不能破坏原有的顺序，那么只能考虑使用滑动窗口实现
     * 1. 暴力解法，超时
     * 没有利用到子数组是连续的这一特性
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }


    /**
     * 前缀和思路，0-k索引的数值和为num1，0-结尾索引的数值和为num2，那么k到结尾的数值和为num2-num1
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum2(int[] nums, int k) {
        // 统计所有的前缀和
        long[] preSum = new long[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
        int sum = 0;
        for (int i = 0; i < preSum.length; i++) {
            // 第一种：从0开始到i和为k；
            if (preSum[i] == k) {
                sum++;
            }
            // 第二种：找从0到i-1有多少前缀和为k - preSum[i]
            for (int j = 0; j < i; j++) {
                if (preSum[i] - preSum[j] == k) {
                    sum++;
                }
            }
        }
        return sum;
    }

    /**
     * 在思路2的基础上使用哈希表进行优化
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum3(int[] nums, int k) {
        // 统计所有的前缀和与出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        int add = 0;
        int r = 0;
        for (int num : nums) {
            add += num;
            if (add == k) {
                r++;
            }
            if (map.containsKey(add - k)) {
                r += map.get(add - k);
            }
            map.put(add, map.getOrDefault(add, 0) + 1);
        }

        return r;
    }

}
